import java.util.*;

public class project {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int len=nums.length;
        int sum=nums[0]+nums[1]+nums[2];
        for(int i=0;i<len;i++){
            int start=i+1;
            int end=len-1;
            while (start<end){
                int tmp=nums[i]+nums[start]+nums[end];
                if(Math.abs(tmp-target)<Math.abs(sum-target)){
                    sum=tmp;
                }
                if(tmp>target){
                    end--;
                }else if(tmp<target){
                    start++;
                }else{
                    return sum;
                }
            }
        }
        return sum;
    }






















    public List<String> letterCombinations(String digits) {
        List<String> list=new ArrayList<>();
        if(digits.length()==0){
            return list;
        }
        Map<Character,String> map=new HashMap<Character,String>(){{
            put('2',"abc");
            put('3',"def");
            put('4',"ghi");
            put('5',"jkl");
            put('6',"mno");
            put('7',"pqrs");
            put('8',"tuv");
            put('9',"wxyz");
        }};
        dfs(list,map,digits,0,new StringBuilder());
        return list;
    }
    public void dfs(List<String> list,Map<Character,String> map,String str,int index,StringBuilder s){
        if(index==str.length()){
            list.add(new String(s));
        }else{
            char ch=str.charAt(index);
            String value=map.get(ch);
            int len=value.length();
            for(int i=0;i<len;i++){
                s.append(value.charAt(i));
                dfs(list,map,str,index+1,s);
                s.deleteCharAt(index);
            }
        }
    }






















    public List<Integer> findKDistantIndices(int[] nums, int key, int k) {
        List<Integer> list=new ArrayList<>();
        int len=nums.length;
        int start=0;
        for(int i=0;i<len;i++){
            if(nums[i]==key){
                start=Math.max(start,i-k);
                int end=Math.min(len-1,i+k);
                while (start<=end){
                    list.add(start);
                    start++;
                }
            }
        }
        return list;
    }

















    public int countHillValley(int[] nums) {
        int flag=0;
        int ret=0;
        for(int i=1;i<nums.length;i++){
            if(nums[i]>nums[i-1]){
                if(flag==1){
                    ret++;
                }
                flag=2;
            }else if(nums[i]<nums[i-1]){
                if(flag==2){
                    ret++;
                }
                flag=1;
            }
        }
        return ret;
    }













    public boolean winnerOfGame(String colors) {
        int A=0;
        int B=0;
        for(int i=0;i<colors.length()-2;i++){
            if(colors.substring(i,i+3).equals("AAA")){
                A++;
            }else if(colors.substring(i,i+3).equals("BBB")){
                B++;
            }
        }
        return A>B;
    }
}
